#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int main()
{
	int tt;
	cin>>tt;
	while(tt--)
	{
		int n,m,r;
		cin>>n>>m>>r;
		bool f[n+5][m+5][r+5];
		for(int i=0;i<=n;i++)
		    for(int j=0;j<=m;j++)
		        for(int k=0;k<=r;k++) 
				    f[i][j][k]=true;
		
		for(int i=1;i<=r;i++)
		{
			int t,d,coord;
			scanf("%d %d %d",&t,&d,&coord);
			if(d==1)
			{
				for(int j=0;j<=m;j++)
				{
					if(0<=t-j-coord && t-j-coord<=r)
					{
						f[coord][j][t-(j+coord)]=false;
					}
				}
			}
			else
			{
				for(int j=0;j<=n;j++)
				{
					if(0<=t-j-coord && t-j-coord<=r)
					{
						f[j][coord][t-(j+coord)]=false;
					}
				}
			}
		}
		
		bool dp[n+5][m+5][r+5];
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=m;j++)
			{
				for(int k=0;k<=r;k++)
				{
					dp[i][j][k]=!(i || j || k);
					if(f[i][j][k])
					{
						if(i>0 && dp[i-1][j][k]) dp[i][j][k]=true;
						if(j>0 && dp[i][j-1][k]) dp[i][j][k]=true;
						if(k>0 && dp[i][j][k-1]) dp[i][j][k]=true;
					}
				}
			}
		}
		int ans=-1;
		for(int i=0;i<=r;i++)
		{
			if(dp[n][m][i]) 
			{
				ans=n+m+i;
				break;
			}
		}
		cout<<ans<<endl;
		        
	}
	

	return 0;
}

